1. Field of the Invention
The present invention relates to a data reading device for reading data stored in a data storage device such as a magnetic disk device or an optical disk device and, more particularly, to a data reading device for reading such data as a video file with constraints on the time from the reception of a data transfer request until the data transfer to a requester.
2. Description of the Related Art
Systems for reading and sending accumulated data at a request from a plurality of users, such as a video server, need to respond to data transfer requests from as many users as possible concurrently. In addition, such a system is required to start sending data in response to a data transfer request and to send the data to the end of a file without intermission.
Commonly used as a video file storage device is a disk device whose storage medium is a magnetic disk or an optical disk. Magnetic disk devices read data written at an arbitrary place on a disk by moving a magnetic head to the place where target data is stored. Disk devices thus require movement of a head for reading data and need a certain time accordingly. Moreover, since a head moving distance differs depending on a storage position of data to be read, it is difficult to estimate a time required for reading data.
In a case where only one file is read in response to one data transfer request instead of responding to a plurality of data transfer requests concurrently, data reading requests to a disk device can be issued in consideration of the time for reading data from the disk device so that data transfer does not terminate halfway. In other words, by predicting a time required for reading each data in a file based on a reading order of each data and a storage position of the data on the disk, appropriate number of data reading requests are issued to the disk device in advance such that subsequent data reading is finished until data transfer interrupts. This prevents data transfer from terminating halfway.
In responding to a plurality of data transfer requests concurrently, however, a reading request can not be issued to a disk device in advance for reading one file. Various means have been therefore proposed for transferring data without intermission to the end of a file.
In the following description, a time required for the data to be read from a disk device, that is, a time at which data transfer interrupts unless reading of the data is finished by that time, is referred to as a deadline time. A time period from a certain time point until a deadline time is referred to as a deadline margin time. A device which issues a data reading request to a data reading device upon receiving a transfer request from a user is referred to as a client. In a video server system which provides the video on demand service, the equivalent of a client is a unit which has the function of accepting commands from a user, issuing reading request corresponding to the commands to a data reading device, converting data read from the data reading device into video data and transferring the data to the user.
In a data reading device of this kind, a maximum data amount (hereinafter referred to as allowable amount) whose reading can be completed within a fixed time period can be computed in advance based on the amount of data (throughput) which is readable from a disk device per unit time. Conventional data reading devices therefore limit the number of clients in advance to prevent the amount of data to be read from exceeding the allowable amount of data of a disk device even when reading requests from a plurality of clients avalanche. This ensures that subsequent data is read from the disk device by a deadline time and enables concurrent data reading in response to reading requests from all the clients.
In addition, the number of clients can be increased by improving a throughput of a disk device. Other conventional data reading devices therefore improve a disk device throughput by providing a cache memory.
Another conventional data reading device is disclosed in Japanese Patent Laying-Open (Kokai) No. Heisei 5-257614. Recited in the literature is a data reading device in which improved throughput is achieved by appropriately changing the order of data reading from a disk device such that the amount of movement of a magnetic head is reduced, thereby shortening a reading time.
In addition, the possibility of data interruption can be reduced by increasing a deadline margin time. In other conventional data reading devices, therefore, a buffer memory is provided at a client and a reading request to a disk device is issued as early as possible to prevent the buffer memory from getting empty.
Any of the above-described conventional data reading devices read data in the order in which a disk device accepts reading requests from clients. In responding to the reading requests from a plurality of clients, however, since deadline margin time varies with each client, it is efficient to give priority to data reading whose reading request has a shorter deadline margin time.
One of conventional data reading devices of this kind is disclosed in Japanese Patent Laying-Open (Kokai) No. Heisei 4-264947. The literature discloses a technique for scheduling the order of data reading according to the priority given to a client. According to the technique, when a client with a shorter deadline margin time and a client with a longer deadline margin time exist together, higher priority is given to the client with a shorter deadline margin time over the client with a longer deadline margin time. Then, data is read from a disk device in the order of the priority according to a deadline margin time. This enables data reading for a higher-priority client with a shorter deadline margin time to be given the priority for reading even when a reading request from a higher-priority client is issued later than a reading request from other lower-priority clients. As a result, a client with a shorter deadline margin time is more unlikely to fail to keep a deadline time.
Image data of moving picture as a processing object in a video server system is ordinarily encoded according to various kinds of encoding formats because the data is of large size. The amount of encoded image data equivalent to image per unit time varies with an encoding format and a data transfer rate varies accordingly. Therefore, in case of dealing with image data of a plurality of kinds of encoding formats in one video server system, multiple transfer rates differing with encoding formats must be achieved simultaneously.
One of conventional techniques of this kind is, for example, a data reading device (video server) disclosed in the article "Video Server Coping with Moving Picture through Expansion of NSF and TCP/IP" (Nikkei Electronics No. 645, pp. 133-141). The article recites a data reading device including queues provided at each client for buffering a reading request to a disk device. This device has queues correspond to transfer rates of data of reading requests stored in the queues. Then, the device achieves various kinds of transfer rates by scheduling the order of choosing a queue to take a reading request from, according to transfer rates.
On the other hand, some moving picture compressing encoding exploits a difference between adjacent images. Such encoding is characterized by high compression rate of image data. However, the amounts of encoded data varies with the contents of image even if the amounts of corresponding original image data are the same. In other words, a transfer rate of encoded data varies depending on data positions even in one video file.
As described in the foregoing, conventional data reading devices, when reading data from a disk device at the request of one client, can avoid interruption of data transfer halfway by predicting a time required for data reading and issuing appropriate number of reading requests to the disk device in advance. In processing reading requests from a plurality of clients concurrently, however, the order of reading requests sent to the disk device is affected by the timing at which data transfer requests arrive at the data reading device or files to be accessed by clients. It is therefore difficult to predict a time required for reading data and accordingly impossible to avoid data transfer interruption by simply issuing reading requests to the disk device in advance.
In addition, conventional data reading devices which avoid data transfer interruption by limiting the number of clients need to reduce the number of clients in consideration of some margin in order to keep a deadline time because the time required for reading data from a disk device is indefinite. The reasons why the time is indefinite are, for example, frequency of data reading requests and a deadline margin time varying with clients, a data reading throughput changing with the amount of movement of a magnetic head and interaction among data reading requests from many clients. Because a data reading time is thus indefinite, the number of clients should be estimated to be small in order to reliably keep a deadline time, which prevents a disk device from being utilized at its full performance.
The conventional data reading devices having cache memories are intended for increasing the number of clients by improving a throughput utilizing localization of data access. Localization of data access, however, can not be expected in such a system dealing with image data of moving picture as a video server due to enormous data size. Cache memories are, therefore, inefficient for video server systems because, the number of clients can not be increased by much.
Increasing a throughput by changing the order of reading data as is implemented by the conventional data reading device disclosed in Japanese Patent Laying-Open (Kokai) No. Heisei 5-257614, has a drawback that a client whose order of data reading is moved down might fail to keep a deadline time.
The conventional data reading devices providing each client with a buffer memory are allowed to have a deadline margin time longer accordingly, thereby reducing the possibility of interruption of data transfer. However, since the disk devices read data in the order of acceptance of reading requests, existence of a client with a long deadline margin time and a client with a short deadline margin time together increases the possibility of data transfer interruption at the client with a short deadline margin. More specifically, when a reading request of the client with a long deadline margin time is accepted prior to that of the client with a short deadline margin time, data reading in response to the reading request accepted later from the client with a short deadline margin time is held over. As a result, clients with a short deadline margin time are more likely to fail to keep a deadline time.
The conventional data reading devices using queues with difference data transmission rates each of which provided at each client are only allowed to provide a single transfer rate for each client. It is, therefore, impossible to cope with a data transmission rate varying with positions in one video file in the system using compressing data encoding based on a difference between adjacent images.